Khu vực lần đầu có con người sinh sống trước năm 350-377 AD (thời đại đồ đá mới muộn). Người bản địa cư trú tại một khu định cư có tên gọi sau này là Himologan[5], cách Cagayan de Oro hiện nay 8 km. Người bản địa theo thuyết vật linh đa thần, có nguồn gốc Nam Đảo cùng với khả năng đi biển tương tự người Bajau. Phong tục của họ có liên hệ mật thiết với Vương quốc Butuan, là nền văn hoá Sri Vijayan (Visayan) và Ấn Độ phong phú. Họ cũng mặc trang phục bộ lạc và truyền thống, quần áo tương tự như ở Bali, Indonesia. Ngoài ra, còn tìm thấy được đồ gốm trong khu vực; người Hoa có lẽ đã đến đây từ thời Tống đến thời Minh.

Năm 1622, các nhà truyền giáo Tây Ban Nha tiếp xúc với người bản địa Himologan và đến năm 1626, Fray Agustín de San Pedro thuyết phục được tù trưởng của Himologan là Datu Salangsang chuyển khu dân cư xuống hạ du sông Cagayan, đến công viên Gaston hiện tại. De San Pedro sau đó củng cố khu dân cư mới nhằm chống lại những tên cướp Sultan Kudarat. Năm 1738, Cagayan de Oro đã nằm trong phạm vi thống trị của Tây Ban Nha một cách chắc chắn. Khi Misamis trở thành một tỉnh vào năm 1818, một trong bốn huyện của tỉnh là Partidos de Cagayan. Năm 1871, "Partidos" trở thành một thị trấn và được xác định làm thủ phủ cố định của Misamis.

Ngày 27 tháng 2 năm 1872, Cagayan trở thành thủ phủ cố định của Segundo Distrito de Misamis. Trong giai đoạn này, tên gọi của thị trấn là Cagayan de Misamis. Năm 1883, thị trấn trở thành trị sở của chính quyền thực dân Tây Ban Nha tại khu vực các tỉnh Misamis Oriental, Misamis Occidental, Bukidnon và Lanao del Norte trên đảo Mindanao. Ngày 10 tháng 1 năm 1899, Cagayan de Misamis gia nhập chính phủ của Emilio Aguinaldo và làm lễ kỷ niệm độc lập từ Tây Ban Nha.

Ngày 31 tháng 3 năm 1900, binh sĩ Hoa Kỳ chiếm lĩnh thị trấn Cagayan de Misamis và đến ngày 7 tháng 4 năm 1900, một trận chiến bùng phát tại trung tâm thị trấn dưới quyền lãnh đạo của Tướng Nicolas Capistrano[6] và quân kháng chiến Philippines, kết quả là người Mỹ chiến thắng. Philippines được độc lập vào ngày 4 tháng 7 năm 1946.[7] Sau những năm rối loạn, hoà bình trở lại khiến cho hoạt động kinh tế được bình thường hoá dưới quyền chỉ đạo của Hoa Kỳ. Kết quả là từ một khu vực thuần nông-ngư nghiệp, Cagayan de Oro nổi lên thành một trung tâm thương nghiệp phát đạt.

Ngày 3 tháng 5 năm 1942, các binh sĩ Hoa Kỳ và Philippines chiến đấu chống lại quân Nhật đến từ Panay. Họ không thể kháng cự vì lực lượng Nhật Bản áp đảo về số lượng và được trang bị tốt hơn, và phải rút đến các địa điểm bên ngoài thành phố. Quân Nhật đốt cháy hầu hết thành phố, đóng quân tại Đại học Ateneo De Cagayan, nay là Đại học Xavier. Người Nhật thi hành chính sách tiêu thổ, còn quân du kích Philippines và Hoa Kỳ vẫn chiến đấu trong giai đoạn này. Máy bay của Hoa Kỳ oanh tạc các căn cứ của quân Nhật vào ngày 10 tháng 10 năm 1944. Liên quân Hoa Kỳ và Philippines đổ bộ tại Cagayan de Oro vào ngày 10 tháng 5 năm 1945.

Ngày 15 tháng 6 năm 1950, Tổng thống Elpidio Quirino cấp quy chế thành phố cho Cagayan de Misamis.[8] Động thái này là nhờ các nỗ lực của nghị sĩ Emmanuel Pelaez đại diện cho Cagayan de Oro.[9] Trong giai đoạn thiết quân luật, Cagayan de Oror không tránh khỏi các vụ đánh bom và việc sử dụng cơ chế tàn bạo chống lại những người bất đồng chính kiến. Đến khi thiết quân luật kết thúc, có khoảng hơn một nghìn người dân của thành phố đã từng bị ngược đãi. Cagayan de Oro trở thành một thành phố đô thị hoá cao độ vào ngày 22 tháng 11 năm 1983. Năm 1986, thành phố tham gia Cách mạng Quyền lực Nhân dân bằng các cuộc tuần hành trên đường phố. Khi Marcos bị lật đổ tại Manila, thành phố nằm trong các địa phương ủng hộ việc đưa Corazon Aquino làm tổng thống.

Ngày 16–17 tháng 12 năm 2011, Bão Washi gây ra lũ quét trên phạm vi lớn tại Bắc Mindanao. Tại Cagayan de Oro, hàng trăm người sống gần bờ sông Cagayan de Oro đã thiệt mạng và mất tích. Các quan chức cho biết một số người đã không sơ tán dù được chính quyền cảnh báo.